#define _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#define vertexnum 100       //定义最大可输入的结点个数
#define QueueMax  100
typedef struct  node        //定义图形的顶点结构 
{
	int  vertex;             //图中的顶点信息为数字
	struct  node* next;
}Graph;
Graph head[vertexnum];      //邻接表的表头结点
int Visited[vertexnum];     //遍历记录
int Front = -1;
int Rear = -1;
int Queue[QueueMax];

int Enqueue(int Vertex)       //元素入队
{
	if (Rear >= QueueMax)       //队列已满
		return -1;
	else
	{
		Rear++;               //队列尾端指针后移
		Queue[Rear] = Vertex;   //将值存入队列中
		return 1;
	}
}

int Dequeue()                //元素出队
{
	if (Front >= Rear)          //队列已空
		return -1;
	else
	{
		Front++;              //队头指针后移
		return Queue[Front];
	}
}

void BFS(int Vertex)//广度优先搜索
{
	Graph* search = &(head[Vertex]);
	while (Vertex != -1) {
		while (search) {
			if (!Visited[search->vertex]) {
				Enqueue(search->vertex);
				Visited[search->vertex] = 1;
			}
			search = search->next;
		}

		search = head[Vertex].next;
		Vertex = Dequeue();
		printf("%d->", Vertex);

}


void Create_l_Graph(int Vertex1, int Vertex2, int no)
{                      //以邻接链表建立图形
	Graph* searchP;     //结点声明
	Graph* New;         //新结点声明 
	New = (Graph*)malloc(sizeof(struct node));
	if (New != NULL)
	{
		New->vertex = Vertex2;
		New->next = NULL;
		searchP = &(head[Vertex1]);
		while (searchP->next != NULL)
			searchP = searchP->next;
		searchP->next = New;
		if (no == 0)
		{
			New = (Graph*)malloc(sizeof(struct node));
			New->vertex = Vertex1;
			New->next = NULL;
			searchP = &(head[Vertex2]);
			while (searchP->next != NULL)
				searchP = searchP->next;
			searchP->next = New;
		}
	}
}

void showmenu()
{                   //显示菜单
	printf("    欢迎使用图的操作演示软件\n");
	printf("\t1、创建图的邻接表\n");
	printf("\t2、图的输出\n");
	printf("\t3、图的广度优先遍历\n");
	printf("\t4、退出程序\n");
}

void print_l_graph(Graph* head)
{                     //输出邻接链表的数据
	Graph* searchP;
	searchP = head->next;
	while (searchP != NULL)
	{
		printf("[%d]", searchP->vertex);
		searchP = searchP->next;
	}
	printf("\n");

}

int main()
{
	int source;           //图中一条边的起始顶点
	int destination;      //图中一条边的终止顶点
	int i, j;
	int vermax;           //定义图中最大的顶点数
	int edgemax;          //定义图中最大的边数
	int choice;
	int no;

	while (1)
	{
		showmenu();
		printf("   请输入你的选择：");
		scanf("%d", &choice);
		fflush(stdin);//清除键盘缓冲区
		switch (choice)
		{
		case 1:printf("请输入图的类别（有向图-1，无向图-0）:");
			scanf("%d", &no);
			printf("请输入图中的总顶点数和边数:");
			scanf("%d%d", &vermax, &edgemax);
			for (i = 1; i < vermax; i++)
			{
				head[i].vertex = i;
				head[i].next = NULL;
			}
			for (i = 1; i <= edgemax; i++)
			{
				printf("请输入第%d条边的起点：", i);
				scanf("%d", &source);
				printf("请输入第%d条边的终点：", i);
				scanf("%d", &destination);
				if (source == destination)
					printf("输入有误！\n");//出错：自身循环
				else                 //调用建立邻接链表
					Create_l_Graph(source, destination, no);
			}
			printf("图创建成功，按任意键继续…\n");
			_getch();
			system("cls");
			break;
		case 2:printf("图的邻接表如下：\n");
			for (i = 1; i <= vermax; i++)
			{
				printf("顶点[%d]:", i);
				print_l_graph(&head[i]);//调用输出邻接链表数据
			}
			printf("\n");
			system("pause");
			system("cls");
			break;
		case 3:for (i = 1; i <= vermax; i++)
			Visited[i] = 0;
			printf("请输入遍历的起点:");
			scanf("%d", &source);
			printf("图的广度优先遍历结果为：\n");
			BFS(source);
			printf("END\n");
			system("pause");
			system("cls");
			break;
		case 4:return;
		default:
			printf("你的输入有误，请从新输入！\n");
			system("pause");
			system("cls");
		}
	}
	return 0;
}
